package s5_递归;

/**
 * @author wisdomelon
 * @date 2020/7/28 0028
 * @project data_study
 * @jdk 1.8
 * 迷宫回溯问题
 */
public class MiGong {

    public static void main(String[] args) {

        // 迷宫地图
        int[][] map = new int[8][7];
        // 使用1 表示墙体
        // 上下至为1
        for(int i=0; i<7; i++) {
            map[0][i]  = 1;
            map[7][i]  = 1;
        }
        // 左右至为1
        for(int i=0; i<8; i++) {
            map[i][0]  = 1;
            map[i][6]  = 1;
        }

        // 设置挡板
        map[5][2]  = 1;
        map[5][3]  = 1;
        map[5][4]  = 1;
        map[6][4]  = 1;
        map[2][4]  = 1;
        map[3][4]  = 1;
        map[4][4]  = 1;

        setWay(map, 1, 1);


        // 输出地图
        for(int i=0; i<8; i++) {
            for(int j=0; j<7; j++) {
                System.out.print(map[i][j] + "\t");
            }
            System.out.println();
        }
    }


    /**
     * 出发点：map[1][1]
     * 结束点： map[6][5]
     * 当map[i][j] = 0 表示还没走  为 1 表示墙体  为2 表示通路 为3 表示已经走过
     * 迷宫策略 下 → 右 → 上 → 左
     * @param map 地图
     * @param i 从哪个位置开始找 出发坐标
     * @param j 从哪个位置开始找 出发坐标
     * @return 找到通路返回true 否则返回false
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if(map[6][5] == 2) {
            // 已经找到终点
            return true;
        }

        // 如果当前点还没走过
        if(map[i][j] == 0) {
            // 假定可以走通
            map[i][j] = 2;
            // 向下
            if(setWay(map, i+1, j)) {
                return true;
            }
            // 向右
            else if(setWay(map, i, j+1)) {
                return true;
            }
            // 向上
            else if(setWay(map, i-1, j)) {
                return true;
            }
            // 向左
            else if(setWay(map, i, j-1)) {
                return true;
            }
            // 说明该点走不通，是死路
            else {
                map[i][j] = 3;
                return false;
            }
        } else {
            return false;
        }
    }

}
